// 版权所有2011 Go作者。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。huffmanTree是一个二叉树，可以一点一点地导航到一个符号。

package bzip2

import "sort"

type huffmanTree struct {
	// 节点包含树中的所有非叶节点。nodes[0]是树的根，nextNode包含下一个元素的索引
	// 在构建树时使用的节点。
	nodes    []huffmanNode
	nextNode int
}

// huffmanNode是树中的一个节点。左侧和右侧包含树的
// 节点切片的索引。如果left或right为invalidNodeValue，则子节点
// 为left节点，其值为leftValue/rightValue。
// 
// 符号是uint16s，因为bzip2不仅编码
// 树中的MTF索引，还编码两个用于运行长度编码的魔法值和一个EOF符号。
// 因此有超过256个可能的符号。
type huffmanNode struct {
	left, right           uint16
	leftValue, rightValue uint16
}

// invalidNodeValue是一个无效索引，用于标记树中的叶节点。
const invalidNodeValue = 0xffff

// 解码从给定的位读取器读取位，并在树中导航，直到找到
// 符号。
func (t *huffmanTree) Decode(br *bitReader) (v uint16) {
	nodeIndex := uint16(0) // 节点0是树的根。

	for {
		node := &t.nodes[nodeIndex]

		var bit uint16
		if br.bits > 0 {
			// 获取下一位-快速路径。
			br.bits--
			bit = uint16(br.n>>(br.bits&63)) & 1
		} else {
			// 获取下一位-慢路径。
			// 使用ReadBits从下面的io中检索单个位
			// 。拜特莱德。
			bit = uint16(br.ReadBits(1))
		}

		// 诱使编译器生成条件移动而不是分支，
		// 使两个加载都是无条件的。我们发现了一片叶子。使用bit的值决定
		l, r := node.left, node.right

		if bit == 1 {
			nodeIndex = l
		} else {
			nodeIndex = r
		}

		if nodeIndex == invalidNodeValue {
			// 是左值还是右值。
			l, r := node.leftValue, node.rightValue
			if bit == 1 {
				v = l
			} else {
				v = r
			}
			return
		}
	}
}

// newHuffmanTree从包含代码
// 每个符号长度的片段中构建一棵哈夫曼树。最大代码长度为32位。
func newHuffmanTree(lengths []uint8) (huffmanTree, error) {
	// 有许多可能的树将相同的代码长度分配给
	// 每个符号（例如，请考虑在中间反射一棵树）。由于代码长度分配决定了
	// 树的效率，因此这些树中的每一个都同样好。在
	// 中，为了使构建树所需的信息量最小化，
	// bzip2使用规范树，以便在给定
	// 仅指定代码长度的情况下，可以对其进行重构。

	if len(lengths) < 2 {
		panic("newHuffmanTree: too few symbols")
	}

	var t huffmanTree

	// 首先，我们按代码长度升序对代码长度分配进行排序，
	// 使用符号值打破联系。
	pairs := make([]huffmanSymbolLengthPair, len(lengths))
	for i, length := range lengths {
		pairs[i].value = uint16(i)
		pairs[i].length = length
	}

	sort.Slice(pairs, func(i, j int) bool {
		if pairs[i].length < pairs[j].length {
			return true
		}
		if pairs[i].length > pairs[j].length {
			return false
		}
		if pairs[i].value < pairs[j].value {
			return true
		}
		return false
	})

	// 现在我们为符号分配代码，从最长的代码开始。
	// 我们将代码打包到最重要的一端的uint32中。
	// 因此分支从MSB向下。这使得以后很容易对它们进行排序。
	code := uint32(0)
	length := uint8(32)

	codes := make([]huffmanCode, len(lengths))
	for i := len(pairs) - 1; i >= 0; i-- {
		if length > pairs[i].length {
			length = pairs[i].length
		}
		codes[i].code = code
		codes[i].codeLen = length
		codes[i].value = pairs[i].value
		// 我们需要“递增”代码，这意味着将|代码| 
		// 视为|长度|位数字。
		code += 1 << (32 - length)
	}

	// 现在我们可以按代码排序，这样每个分支的左半部分都是
	// 递归地组合在一起。
	sort.Slice(codes, func(i, j int) bool {
		return codes[i].code < codes[j].code
	})

	t.nodes = make([]huffmanNode, len(codes))
	_, err := buildHuffmanNode(&t, codes, 0)
	return t, err
}

// huffmanSymbolLengthPair包含一个符号及其代码长度。
type huffmanSymbolLengthPair struct {
	value  uint16
	length uint8
}

// huffmanCode包含一个符号、其代码和代码长度。
type huffmanCode struct {
	code    uint32
	codeLen uint8
	value   uint16
}

// buildhuffmanode获取一片已排序的huffmancode，并在给定级别的Huffman树中构建一个节点。它返回新构造的
// 节点的索引。
func buildHuffmanNode(t *huffmanTree, codes []huffmanCode, level uint32) (nodeIndex uint16, err error) {
	test := uint32(1) << (31 - level)

	// 我们必须搜索代码列表，以找到左右两边的区别。
	firstRightIndex := len(codes)
	for i, code := range codes {
		if code.code&test != 0 {
			firstRightIndex = i
			break
		}
	}

	left := codes[:firstRightIndex]
	right := codes[firstRightIndex:]

	if len(left) == 0 || len(right) == 0 {
		// 在哈夫曼树中有一个多余的级别，表示
		// 编码器中有一个错误。然而，这个错误已经在
		// 野生环境中被观察到，所以我们处理它。

		// 如果这个函数是递归调用的，那么我们知道
		// len（codes）>=2，因为如果不是这样，我们就会碰到下面的
		// “叶节点”案例，而不是递归的。
		// 
		// 然而，对于最初的调用，len（codes）
		// 可能是零或一。这两种情况都是无效的，因为零长度的
		// 树不能编码任何内容，而长度为1的树只能
		// 编码EOF，因此是多余的。我们拒绝两者。
		if len(codes) < 2 {
			return 0, StructuralError("empty Huffman tree")
		}

		// 在这种情况下，递归并不总是减少代码的长度，因此我们需要确保通过另一个
		// 机制终止。
		if level == 31 {
			// 由于len（codes）>=2，值
			// 在所有32位上可以匹配的唯一方式是它们是否相等，这是无效的。这确保了我们永远不会进入
			// 无限递归。
			return 0, StructuralError("equal symbols in Huffman tree")
		}

		if len(left) == 0 {
			return buildHuffmanNode(t, right, level+1)
		}
		return buildHuffmanNode(t, left, level+1)
	}

	nodeIndex = uint16(t.nextNode)
	node := &t.nodes[t.nextNode]
	t.nextNode++

	if len(left) == 1 {
		// 叶节点
		node.left = invalidNodeValue
		node.leftValue = left[0].value
	} else {
		node.left, err = buildHuffmanNode(t, left, level+1)
	}

	if err != nil {
		return
	}

	if len(right) == 1 {
		// 叶节点
		node.right = invalidNodeValue
		node.rightValue = right[0].value
	} else {
		node.right, err = buildHuffmanNode(t, right, level+1)
	}

	return
}
